{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Queries on a Permutation With Key"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-indexed-tree #array #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树状数组 #数组 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: processQueries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #查询带键的排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个正整数数组&nbsp;<code>queries</code> ，其取值范围在&nbsp;<code>1</code> 到 <code>m</code> 之间。 请你根据以下规则按顺序处理所有&nbsp;<code>queries[i]</code>（从 <code>i=0</code> 到 <code>i=queries.length-1</code>）：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>首先，你有一个排列&nbsp;<code>P=[1,2,3,...,m]</code>。</li>\n",
    "\t<li>对于当前的 <code>i</code> ，找到&nbsp;<code>queries[i]</code> 在排列 <code>P</code> 中的位置（<b>从 0 开始索引</b>），然后将它移到排列&nbsp;<code>P</code> 的开头（即下标为 0 处）。注意， <code>queries[i]</code>&nbsp;的查询结果是 <code>queries[i]</code> 在 <code>P</code> 中移动前的位置。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回一个数组，包含从给定 &nbsp;<code>queries</code>&nbsp;中查询到的结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>queries = [3,1,2,1], m = 5\n",
    "<strong>输出：</strong>[2,1,2,1] \n",
    "<strong>解释：处理</strong> queries 的过程如下：\n",
    "对于 i=0: queries[i]=3, P=[1,2,3,4,5], 3 在 P 中的位置是 <strong>2</strong>，然后我们把 3 移动到 P 的开头，得到 P=[3,1,2,4,5] 。\n",
    "对于 i=1: queries[i]=1, P=[3,1,2,4,5], 1 在 P 中的位置是 <strong>1</strong>，然后我们把 1 移动到 P 的开头，得到 P=[1,3,2,4,5] 。 \n",
    "对于 i=2: queries[i]=2, P=[1,3,2,4,5], 2 在 P 中的位置是 <strong>2</strong>，然后我们把 2 移动到 P 的开头，得到 P=[2,1,3,4,5] 。\n",
    "对于 i=3: queries[i]=1, P=[2,1,3,4,5], 1 在 P 中的位置是 <strong>1</strong>，然后我们把 1 移动到 P 的开头，得到 P=[1,2,3,4,5] 。 \n",
    "因此，包含结果的数组为 [2,1,2,1] 。  \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>queries = [4,1,2,2], m = 4\n",
    "<strong>输出：</strong>[3,1,2,0]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>queries = [7,5,5,8,3], m = 8\n",
    "<strong>输出：</strong>[6,5,0,7,5]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= m &lt;= 10^3</code></li>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= m</code></li>\n",
    "\t<li><code>1 &lt;= queries[i] &lt;= m</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [queries-on-a-permutation-with-key](https://leetcode.cn/problems/queries-on-a-permutation-with-key/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [queries-on-a-permutation-with-key](https://leetcode.cn/problems/queries-on-a-permutation-with-key/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,1,2,1]\\n5', '[4,1,2,2]\\n4', '[7,5,5,8,3]\\n8']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        res = []\n",
    "        s = list(range(1, m + 1))\n",
    "        for i in queries:\n",
    "            res.append(s.index(i))\n",
    "            s.remove(i)\n",
    "            s.insert(0, i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        dic = [i for i in range(1,m+1)]\n",
    "        ans = []\n",
    "        for j in queries:\n",
    "            index = dic.index(j)\n",
    "            ans.append(index)\n",
    "            dic.remove(j)\n",
    "            dic.insert(0, j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        P = list(range(1, m+1))\n",
    "        ans = []\n",
    "        for i in queries:\n",
    "            target = P.index(i)\n",
    "            ans.append(target)\n",
    "            P.pop(target)\n",
    "            P.insert(0, i)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        P = list(range(1,m+1))\n",
    "        ans = []\n",
    "        for i in range(len(queries)):\n",
    "            x = P.index(queries[i])\n",
    "            ans.append(x)\n",
    "            P.pop(x)\n",
    "            P.insert(0,queries[i])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        p = [x + 1 for x in range(m)]\n",
    "        ans = list()\n",
    "        for query in queries:\n",
    "            pos = -1\n",
    "            for i in range(m):\n",
    "                if p[i] == query:\n",
    "                    pos = i\n",
    "                    break\n",
    "            ans.append(pos)\n",
    "            p.pop(pos)\n",
    "            p.insert(0, query)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.a = [0] * (n + 1)\n",
    "    \n",
    "    @staticmethod\n",
    "    def lowbit(x):\n",
    "        return x & (-x)\n",
    "    \n",
    "    def query(self, x):\n",
    "        ret = 0\n",
    "        while x > 0:\n",
    "            ret += self.a[x]\n",
    "            x -= BIT.lowbit(x)\n",
    "        return ret\n",
    "    \n",
    "    def update(self, x, dt):\n",
    "        while x <= self.n:\n",
    "            self.a[x] += dt\n",
    "            x += BIT.lowbit(x)\n",
    "        \n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        n = len(queries)\n",
    "        bit = BIT(m + n)\n",
    "        \n",
    "        pos = [0] * (m + 1)\n",
    "        for i in range(1, m + 1):\n",
    "            pos[i] = n + i\n",
    "            bit.update(n + i, 1)\n",
    "        \n",
    "        ans = list()\n",
    "        for i, query in enumerate(queries):\n",
    "            cur = pos[query]\n",
    "            bit.update(cur, -1)\n",
    "            ans.append(bit.query(cur))\n",
    "            cur = pos[query] = n - i\n",
    "            bit.update(cur, 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        ans = []\n",
    "        p = list(range(1,m+1))\n",
    "        for i in range(0,len(queries)):\n",
    "            num = p.index(queries[i])\n",
    "            ans.append(num)\n",
    "            del p[num]\n",
    "            p.insert(0,queries[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        p_tmp = [i for i in range(1, m+1)]\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for i in queries:\n",
    "            index = p_tmp.index(i)\n",
    "            p_tmp.remove(i)\n",
    "            p_tmp.insert(0, i)\n",
    "            res.append(index)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        n = len(queries)\n",
    "        tree, pos, ans = [0] * (n+m+1), [0] * (m+1), [0] * n\n",
    "\n",
    "        def query(u: int) -> int:\n",
    "            res = 0\n",
    "            while u:\n",
    "                res += tree[u]\n",
    "                u -= u & -u\n",
    "            return res\n",
    "\n",
    "        def update(u: int, v: int) -> None:\n",
    "            while u < len(tree):\n",
    "                tree[u] += v\n",
    "                u += u & -u\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            pos[i] = n+i\n",
    "            update(n+i, 1)\n",
    "        for i, e in enumerate(queries):\n",
    "            update(pos[e], -1)\n",
    "            ans[i] = query(pos[e])\n",
    "            pos[e] = n-i\n",
    "            update(pos[e], 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        ans=[i for i in range(1,m+1)]\n",
    "        array=[]\n",
    "        for i in queries:\n",
    "            for j in range(len(ans)):\n",
    "                if i==ans[j]:\n",
    "                    array.append(j)\n",
    "                    ans.remove(i)\n",
    "                    ans.insert(0,i)\n",
    "                    break\n",
    "        return array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        P = list(range(1,m+1))\n",
    "        ans = []\n",
    "        for i in range(len(queries)):\n",
    "            x = P.index(queries[i])\n",
    "            ans.append(x)\n",
    "            for j in range(x,0,-1):\n",
    "                P[j] = P[j-1]\n",
    "            P[0] = queries[i]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        p=[i+1 for i in range(m)]\n",
    "        res = []\n",
    "        # for i in range(1,m+1):\n",
    "        #     p.append(i)\n",
    "        for i in queries:\n",
    "            for j,v in enumerate(p):\n",
    "                if v == i:\n",
    "                    res.append(j)\n",
    "                    p.pop(j)\n",
    "                    p.insert(0,i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        p = [x + 1 for x in range(m)]\n",
    "        ans = list()\n",
    "        for query in queries:\n",
    "            pos = -1\n",
    "            for i in range(m):\n",
    "                if p[i] == query:\n",
    "                    pos = i\n",
    "                    break\n",
    "\n",
    "            ans.append(pos)\n",
    "            p.pop(pos)\n",
    "            p.insert(0, query)\n",
    "            \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        ans = []\n",
    "        p = list(range(1, m + 1))\n",
    "        for x in queries:\n",
    "            i = p.index(x)\n",
    "            ans.append(i)\n",
    "            p.pop(i)\n",
    "            p.insert(0, x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        P = list(i for i in range(1, m + 1))\n",
    "\n",
    "        res = []\n",
    "        for query in queries:\n",
    "            print(P)\n",
    "            index = P.index(query)\n",
    "            res.append(index)\n",
    "            P.remove(query)\n",
    "            P = [query] + P\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        res = []\n",
    "        p = list(range(1,m+1))\n",
    "        for i in range(len(queries)):\n",
    "            k = p.index(queries[i])\n",
    "            res.append(k)\n",
    "            p.pop(k)\n",
    "            p.insert(0,queries[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        # 初始化排列 P\n",
    "        P = [i for i in range(1, m + 1)]\n",
    "        \n",
    "        # 初始化结果数组\n",
    "        result = []\n",
    "        \n",
    "        # 遍历待查数组 queries\n",
    "        for q in queries:\n",
    "            # 查找 q 在 P 中的位置\n",
    "            index = P.index(q)\n",
    "            \n",
    "            # 将结果添加到结果数组中\n",
    "            result.append(index)\n",
    "            \n",
    "            # 将元素移动到 P 的起始位置\n",
    "            P.pop(index)\n",
    "            P.insert(0, q)\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        res = []\n",
    "        p = list(range(1,m+1))\n",
    "        for i in range(len(queries)):\n",
    "            idx = p.index(queries[i])\n",
    "            res.append(idx)\n",
    "            for j in range(idx,0,-1):\n",
    "                p[j],p[j-1] = p[j-1],p[j]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "\n",
    "        p = [x + 1 for x in range(m)]\n",
    "        res = []\n",
    "\n",
    "        for querie in queries:\n",
    "            pos = -1\n",
    "            for i in range(m):\n",
    "                if p[i] == querie:\n",
    "                    pos = i\n",
    "                    break\n",
    "            res.append(pos)\n",
    "            p.pop(pos)\n",
    "            p.insert(0, querie)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        P=[]\n",
    "        for i in range(1,m+1):\n",
    "            P.append(i)\n",
    "        #print(P)\n",
    "        res=[]\n",
    "        for query in queries:\n",
    "            index=P.index(query)\n",
    "            res.append(index)\n",
    "            P=[query]+P[:index]+P[index+1:]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "\n",
    "\n",
    "        stk = [i+1 for i in range(m)]\n",
    "\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            idx = stk.index(q)\n",
    "            stk = [q] + stk[:idx] + stk[idx+1:]\n",
    "            ans.append(idx)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "\n",
    "        p = [x + 1 for x in range(m)]\n",
    "        res = []\n",
    "\n",
    "        for querie in queries:\n",
    "            pos = -1\n",
    "            for i in range(m):\n",
    "                if p[i] == querie:\n",
    "                    pos = i\n",
    "                    break\n",
    "            res.append(pos)\n",
    "            p.pop(pos)\n",
    "            p.insert(0, querie)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):# 初始化树状数组长度和树状数组\n",
    "        self.n = n\n",
    "        self.a = [0] * (n + 1)\n",
    "    \n",
    "    def lowbit(x):# 定义lowbit操作\n",
    "        return x & (-x)\n",
    "    \n",
    "    def query(self, x):# 求区间和\n",
    "        ret = 0\n",
    "        while x > 0:\n",
    "            ret += self.a[x]\n",
    "            x -= BIT.lowbit(x)\n",
    "        return ret\n",
    "    \n",
    "    def update(self, x, dt):# 修改单个数据，需要修改所有祖先的数据\n",
    "        while x <= self.n:\n",
    "            self.a[x] += dt\n",
    "            x += BIT.lowbit(x)\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        n = len(queries)\n",
    "        bit = BIT(m + n)\n",
    "        \n",
    "        # 初始化树状数组的后m项，从下标为n + 1开始\n",
    "        pos = [0] * (m + 1)\n",
    "        for i in range(1, m + 1):\n",
    "            pos[i] = n + i\n",
    "            bit.update(n + i, 1)\n",
    "        \n",
    "        ans = list()\n",
    "        for i, query in enumerate(queries):\n",
    "            cur = pos[query]\n",
    "            bit.update(cur, -1)# 置为0，表示为空\n",
    "            ans.append(bit.query(cur))# 区间和，由于每个元素有则都是1，所以就是1的个数，从而映射出当前位置\n",
    "            cur = pos[query] = n - i# 找到元素移入位置，也就是n-i，同时更新pos数组\n",
    "            bit.update(cur, 1)# 将n-i出元素置为1，表示存在\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        p = []\n",
    "        ans = []\n",
    "        for i in range(1, m+1):     #建立一个顺序列表\n",
    "            p.append(i)\n",
    "        for e in queries:\n",
    "            a = p.index(e)        #找到对应索引，写入答案\n",
    "            ans.append(a)\n",
    "            p.pop(a)                #处理后的数移动到列表最前端\n",
    "            p.insert(0, e)        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        p = [x + 1 for x in range(m)]\n",
    "        ans = list()\n",
    "        for query in queries:\n",
    "            pos = -1\n",
    "            for i in range(m):\n",
    "                if p[i] == query:\n",
    "                    pos = i\n",
    "                    break\n",
    "            ans.append(pos)\n",
    "            p.pop(pos)\n",
    "            p.insert(0, query)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        dict1 = {x:x-1 for x in range(1,m+1)}\n",
    "\n",
    "        res = []\n",
    "        for i in queries:\n",
    "            index = dict1[i]\n",
    "            res.append(index)\n",
    "            for x,y in dict1.items():\n",
    "                if y < index:\n",
    "                    dict1[x] += 1\n",
    "                elif y == index:    \n",
    "                    dict1[x] = 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        p = [x + 1 for x in range(m)]\n",
    "        ans = []\n",
    "        for query in queries:        \n",
    "            for i in range(m):\n",
    "                if p[i] == query:   \n",
    "                    break\n",
    "            p.pop(i)\n",
    "            ans.append(i)\n",
    "            p.insert(0,query)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        P = list(range(1, m+1))\n",
    "        ans = []\n",
    "        for i in queries:\n",
    "            target = P.index(i)\n",
    "            ans.append(target)\n",
    "            P = [i] + P[:target] + P[target+1:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        p = [x + 1 for x in range(m)]\n",
    "        ans = list()\n",
    "        for query in queries:\n",
    "            pos = -1\n",
    "            for i in range(m):\n",
    "                if p[i] == query:\n",
    "                    pos = i\n",
    "                    break\n",
    "            ans.append(pos)\n",
    "            p.pop(pos)\n",
    "            p.insert(0, query)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        p = list(range(m+1))[1:]\n",
    "        out =[]\n",
    "        for i in queries:\n",
    "            cur = 0\n",
    "            for t in p:\n",
    "                if t == i:\n",
    "                    p = [p[cur]] + p[:cur] + p[cur+1:]\n",
    "                    out += [cur]\n",
    "                    break\n",
    "                cur += 1\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        p = [i for i in range(1,m+1)]\n",
    "        nlen = len(queries)\n",
    "        res = [0] * nlen\n",
    "        for i in range(nlen):\n",
    "            idx = p.index(queries[i])\n",
    "            res[i] = idx\n",
    "            del p[idx]\n",
    "            p.insert(0,queries[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        # 初始化排列 P\n",
    "        P = [i for i in range(1, m + 1)]\n",
    "        \n",
    "        # 初始化结果数组\n",
    "        result = []\n",
    "        \n",
    "        # 遍历待查数组 queries\n",
    "        for q in queries:\n",
    "            # 查找 q 在 P 中的位置\n",
    "            index = P.index(q)\n",
    "            \n",
    "            # 将结果添加到结果数组中\n",
    "            result.append(index)\n",
    "            \n",
    "            # 将元素移动到 P 的起始位置\n",
    "            P.pop(index)\n",
    "            P.insert(0, q)\n",
    "        \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        # 初始化排列 P\n",
    "        P = [i for i in range(1, m + 1)]\n",
    "        \n",
    "        # 初始化结果数组\n",
    "        result = []\n",
    "        \n",
    "        # 遍历待查数组 queries\n",
    "        for q in queries:\n",
    "            # 查找 q 在 P 中的位置\n",
    "            index = P.index(q)\n",
    "            \n",
    "            # 将结果添加到结果数组中\n",
    "            result.append(index)\n",
    "            \n",
    "            # 将元素移动到 P 的起始位置\n",
    "            P.pop(index)\n",
    "            P.insert(0, q)\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        nums = [i + 1 for i in range(m)]\n",
    "        res = []\n",
    "        for query in queries:\n",
    "\n",
    "            index1 = nums.index(query)\n",
    "            val = nums.pop(index1)\n",
    "            nums.insert(0, val)\n",
    "\n",
    "            res.append(index1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.a = [0] * (n + 1)\n",
    "    \n",
    "    @staticmethod\n",
    "    def lowbit(x):\n",
    "        return x & (-x)\n",
    "    \n",
    "    def query(self, x):\n",
    "        ret = 0\n",
    "        while x > 0:\n",
    "            ret += self.a[x]\n",
    "            x -= BIT.lowbit(x)\n",
    "        return ret\n",
    "    \n",
    "    def update(self, x, dt):\n",
    "        while x <= self.n:\n",
    "            self.a[x] += dt\n",
    "            x += BIT.lowbit(x)\n",
    "        \n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        n = len(queries)\n",
    "        bit = BIT(m + n)\n",
    "        \n",
    "        pos = [0] * (m + 1)\n",
    "        for i in range(1, m + 1):\n",
    "            pos[i] = n + i\n",
    "            bit.update(n + i, 1)\n",
    "        \n",
    "        ans = list()\n",
    "        for i, query in enumerate(queries):\n",
    "            cur = pos[query]\n",
    "            bit.update(cur, -1)\n",
    "            ans.append(bit.query(cur))\n",
    "            cur = pos[query] = n - i\n",
    "            bit.update(cur, 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        num = list(range(1,m+1))\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            # if q<1 or q>m:\n",
    "            #     continue\n",
    "            idx = num.index(q)\n",
    "            ans.append(idx)\n",
    "            num .pop(idx)\n",
    "            num.insert(0, q) \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        r = [i + 1 for i in range(m)]\n",
    "        print(r)\n",
    "        ret = []\n",
    "        for q in queries:\n",
    "            for j in range(m):\n",
    "                if r[j] == q:\n",
    "                    ret.append(j)\n",
    "                    r = [r[j]] + r[:j] + r[j + 1:]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# 模拟\n",
    "class Solution1:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        lst = list(range(1, m+1))\n",
    "        ans = []\n",
    "        for num in queries:\n",
    "            ans.append(lst.index(num))\n",
    "            lst.insert(0, lst.pop(ans[-1]))\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "class Solution12:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        p = [x + 1 for x in range(m)]\n",
    "        ans = list()\n",
    "        for query in queries:\n",
    "            pos = -1\n",
    "            for i in range(m):\n",
    "                if p[i] == query:\n",
    "                    pos = i\n",
    "                    break\n",
    "\n",
    "            ans.append(pos)\n",
    "            p.pop(pos)\n",
    "            p.insert(0, query)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "# 树状数组\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.a = [0] * (n + 1)\n",
    "    \n",
    "    @staticmethod\n",
    "    def lowbit(x):\n",
    "        return x & (-x)\n",
    "    \n",
    "    def query(self, x):\n",
    "        ret = 0\n",
    "        while x > 0:\n",
    "            ret += self.a[x]\n",
    "            x -= BIT.lowbit(x)\n",
    "\n",
    "        return ret\n",
    "    \n",
    "    def update(self, x, dt):\n",
    "        while x <= self.n:\n",
    "            self.a[x] += dt\n",
    "            x += BIT.lowbit(x)\n",
    "        \n",
    "class Solution3:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        n = len(queries)\n",
    "        bit = BIT(m + n)\n",
    "        \n",
    "        pos = [0] * (m + 1)\n",
    "        for i in range(1, m + 1):\n",
    "            pos[i] = n + i\n",
    "            bit.update(n + i, 1)\n",
    "        \n",
    "        ans = list()\n",
    "        for i, query in enumerate(queries):\n",
    "            cur = pos[query]\n",
    "            bit.update(cur, -1)\n",
    "            ans.append(bit.query(cur))\n",
    "            cur = pos[query] = n - i\n",
    "            bit.update(cur, 1)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "# 单点更新与前缀求和\n",
    "class TreeArray:\n",
    "    # 数组索引从1开始\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.c = [0]*(n+1)\n",
    "\n",
    "    # 求x的二进制表示中，最低位的1的位置对应的数，向右相加更新管辖值，向左相减获得前缀和\n",
    "    @staticmethod\n",
    "    def lowest_bit(x):\n",
    "        return x & -x\n",
    "\n",
    "    # 给nums索引x增加k，同时维护对应受到影响的区间和c数组\n",
    "    def add(self, x, k):\n",
    "        while x <= self.n:  # 不能越界\n",
    "            self.c[x] = self.c[x] + k\n",
    "            x = x + self.lowest_bit(x)\n",
    "        return\n",
    "\n",
    "    # 前缀求和\n",
    "    def get_sum(self, x):  # a[1]..a[x]的和\n",
    "        ans = 0\n",
    "        while x >= 1:\n",
    "            ans += self.c[x]\n",
    "            x -= self.lowest_bit(x)\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def processQueries(self, queries: List[int], m: int) -> List[int]:\n",
    "        n = len(queries)\n",
    "        tree_array = TreeArray(n+m)\n",
    "        ind = dict()\n",
    "        for i in range(1, m+1):\n",
    "            tree_array.add(i+n, 1)\n",
    "            ind[i] = i+n\n",
    "\n",
    "        ans = []\n",
    "        null = n\n",
    "        for num in queries:\n",
    "            # 查询前面有几个数，即当前数num的位置索引\n",
    "            ans.append(tree_array.get_sum(ind[num]-1))\n",
    "            # 将当前数的位置归0，同时移到最前面\n",
    "            tree_array.add(ind[num], -1)\n",
    "            ind[num] = null\n",
    "            null -= 1\n",
    "            tree_array.add(ind[num], 1)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
